package com.future;

/**
 * Description: 1289. 下降路径最小和  II
 * [
 * [-73,61,43,-48,-36],
 * [3,30,27,57,10],
 * [96,-76,84,59,-15],
 * [5,-49,76,31,-7],
 * [97,91,61,-46,67]
 * ]
 *
 * @author weiruibai.vendor
 * Date: 2023/2/17 17:42
 */
public class Solution_1289 {

    static Solution_1289 instance = new Solution_1289();

    public static void main(String[] args) {
        int[][] grid = new int[][]{
                {-73, 61, 43, -48, -36},
                {3, 30, 27, 57, 10},
                {96, -76, 84, 59, -15},
                {5, -49, 76, 31, -7},
                {97, 91, 61, -46, 67}
        };
        System.out.println(instance.minFallingPathSum(grid));
    }

    public int minFallingPathSum(int[][] grid) {
        int N = grid.length;
        int M = grid[0].length;
        int[][] dp = new int[N][M];
        for (int i = 0; i < M; i++) {
            dp[0][i] = grid[0][i];
        }
        for (int i = 1; i < N; i++) {
            for (int j = 0; j < M; j++) {
                int min = Integer.MAX_VALUE;
                for (int k = 0; k < M; k++) {
                    if (k == j) continue;
                    min = Math.min(min, dp[i - 1][k]);
                }
                dp[i][j] = min + grid[i][j];
            }
        }
        int ans = Integer.MAX_VALUE;
        for (Integer num : dp[N - 1]) {
            ans = Math.min(ans, num);
        }
        return ans;
    }
}
